package listnode;


import listnode.data.ListNode;

import java.util.PriorityQueue;

/**
 * 合并 K 个升序链表
 *
 * 1.分治合并
 *
 * 2.优先队列
 */
public class MergeKLists2 {

    class SortListNode implements Comparable<SortListNode> {

        public ListNode ptr;

        public SortListNode(ListNode ptr) {
            this.ptr=ptr;
        }

        @Override
        public int compareTo(SortListNode o) {
            return ptr.val-o.ptr.val;
        }
    }

    PriorityQueue<SortListNode> queue=new PriorityQueue<>();

    //[[1,4,5],[1,3,4],[2,6]]
    public ListNode mergeKLists(ListNode[] lists) {
        for (int i = 0; i < lists.length; i++) {

            ListNode ptr=lists[i];
            while (ptr!=null){
                queue.add(new SortListNode(ptr));
                ptr=ptr.next;
            }
        }


        ListNode head=new ListNode(-1);


        ListNode cur=head;

        while (!queue.isEmpty()){
            ListNode next=queue.poll().ptr;
            cur.next=next;
            cur=cur.next;
        }
        //防止回环
        cur.next=null;

        return head.next;
    }

}
